1. Field of the Invention
The present invention relates to an apparatus and a method for generating a figure and, more particularly, to an apparatus and a method for generating a figure of the kind which approximates the contour of a figure defined by a parametric cubic curve by use of segments of a straight line.
2. Description of the Prior Art
Generally, a display, printer or similar image output terminal renders a desired figure by using a curve whose rectangular coordinates are represented by a parameter t, e.g. a parametric cubic curve as typified by a Bezier curves or a spline curve. FIG. 2 shows an example of vector fonts. In FIG. 2, the curves each interconnecting crosses are the parametric cubic curves. One approach to approximate such a curve represented by a parametric cubic curve is recurrently subdividing a Bezier curve which is defined by four control points into two curve segments each being defined by four points, as taught by Newman, William M. in "PRINCIPLES OF INTERACTIVE COMPUTER GRAPHICS", McGraw-Hill, pp. 328-329 (1979) by way of example.
Specifically, as shown in FIG. 3A, assume a Bezier curve which is defined by four control points P.sub.0, P.sub.1, P.sub.2 and P.sub.3. Then, the above-mentioned approach divides the Bezier curve into two curve segments each being defined by four control points, as shown in FIG. 3B. As FIG. 3C indicates, the original Bezier curve is approximated by conjugate straight line segments each interconnecting the opposite ends of respective one of the curve segments. Such a subdividing technique is further effected with each of the curve segments recurrently until successive straight line segments having a desired degree of accuracy have been produced.
A Bezier curve stated above may be subdivided by the following procedure. Assume that the control points of the original curve are P.sub.i =(x.sub.i, y.sub.i) (where i=0 to 3), and that the control points of the left half of the subdivided curve are P'.sub.i =(x'.sub.i, y'.sub.i), then control points P'.sub.0 to P'.sub.3 are produced by: EQU P'.sub.0 =P.sub.0 EQU P'.sub.1 =P.sub.0 /2+P.sub.1 /2 EQU P'.sub.2 =P.sub.0 /4+P.sub.1 /2+P.sub.2 /4 EQU P'.sub.3 =P.sub.0 /8+3P.sub.1 /8+3P.sub.2 /8+P.sub.3 /8.
This may be represented by a matrix: ##EQU1## Likewise, the control points of the right half of the subdivided curve may be represented by a matrix: ##EQU2##
The prior art approximating method sequentially subdivides a Bezier curve recurrently starting at four control points, as discussed above. This brings about a problem that a so-called binary-tree data structure is constructed during the course of subdivision, resulting in the need for an extra work area and extra data supervision. Further, the binary-tree data structure is not readily adaptive to the processing for developing pixels in a raster memory of a raster device according to the order of scanning lines. The prior art method is, therefore, not feasible for a mode wherein the contour of a vector font is approximated by straight line segments and the inside of the resulting font area is sequentially painted out by scanning lines. With the prior art method, it is necessary that four different x coordinates representative of four control points have to be multiplied by a 4.times.4 matrix each, during every recurrent subdivision. A lot of calculations are also required for estimating the accuracy in the approximation. This kind of procedure involves a prohibitive number of recurrent subdivisions and, therefore, a prohibitive number of calculations, especially when a character font which inherently attaches much importance to the accuracy of approximation is to be drawn or generated.